package com.leetcode;

import java.util.Arrays;

/**
 * 1738. 找出第 K 大的异或坐标值
 *
 * @author yml
 *
 */
public class LeetCode1738 {

	public static void main(String[] arg0) {
		int[][] a = new int[2][2];
		a[0][0] = 5;
		a[0][1] = 2;
		a[1][0] = 1;
		a[1][1] = 6;
		int k = 4;
		System.out.println("结果第" + k + "大坐标值  = " + kthLargestValue(a, k));
	}

	public static int kthLargestValue(int[][] matrix, int k) {
		int m = matrix.length;
		int n = matrix[0].length;

		int[][] xorMatrix = new int[m + 1][n];
		int[] maxk = new int[k];
		int i = 0;
		for (int a = 0; a < m; a++) {
			for (int b = 0; b < n; b++) {
				if (a == 0 && b == 0) {
					xorMatrix[m][0] = matrix[0][0];
					xorMatrix[a][b] = matrix[0][0];
					maxk[i] = xorMatrix[a][b];
					i++;
					continue;
				}
				if (a == 0) {
					xorMatrix[m][b] = matrix[0][b];
					xorMatrix[a][b] = xorMatrix[a][b - 1] ^ matrix[a][b];
				} else {
					xorMatrix[m][b] = xorMatrix[m][b] ^ matrix[a][b];
					if (b == 0) {
						xorMatrix[a][b] = xorMatrix[m][b];
					} else {
						xorMatrix[a][b] = xorMatrix[a][b - 1] ^ xorMatrix[m][b];
					}
				}

				if (i < k) {
					maxk[i] = xorMatrix[a][b];
					i++;
					if (i == k && k > 1) {
						Arrays.sort(maxk);
					}
				} else if (i >= k) {
					if (xorMatrix[a][b] > maxk[0]) {
						maxk[0] = xorMatrix[a][b];
						if (k > 1) {
							for (int j = 1; j < k; ++j) {
								if (xorMatrix[a][b] > maxk[j]) {
									maxk[j - 1] = maxk[j];
									maxk[j] = xorMatrix[a][b];
								} else {
									break;
								}
							}
						}
					}
				}
				System.out.println(Arrays.toString(maxk));

			}
		}

		return maxk[0];
	}

}
